This application claims benefit of priority of Foreign Patent Application No. 201010150075.X, filed in China on Apr. 16, 2010, which is herein incorporated by reference.
The present invention relates to a technology for deadlock detection in a program and more particularly relates to a technology for detecting deadlock in a program through lock graph analysis.
Process (thread) deadlock in a computer program is a very fatal problem. Process (thread) deadlock refers to a phenomenon where two or more processes (threads) are waiting for each other, which is caused by the two or more processes (threads) competing on a shared resource during execution. Unless a process (thread) to which deadlock occurs abandons the shared resource, two or more transactions in the deadlock have to wait indefinitely. The process (thread) deadlock will usually cause breakdown of the whole system. Many factors exist triggering process (thread) deadlock, mainly comprising (1) limited system resources, (2) an improper sequence for executing processes (threads), and (3) improper resource allocation. If the system resources are sufficient and all process requests for resources can be satisfied, the possibility of deadlock will be low; otherwise, striving for the limited resources will result into deadlock. Furthermore, differences in process running and advancing sequence and speed may also cause deadlock. In order to prevent process (thread) deadlock from causing serious damage to the whole system and to improve system stability, an efficient method for detecting deadlock is desirable so as to find process (thread) deadlock in time and adopt proper measures to release deadlock, thereby avoiding further deterioration of the system running condition.
Currently, the prior art has proposed a graph theory based deadlock detection method. A graph intuitively representing a deadlock state is constructed by recording lock events during the execution of a computer program, for example, lock graph and resource allocation graph. In a lock graph, a node denotes a lock of resources, and a directed edge pointing from one node to another node indicates that a process having obtained a lock of a certain resource is requesting a lock of another resource. Specifically speaking, a directed edge indicates that a process having obtained a lock of a certain resource at a particular program location (for example, lines of program codes) will obtain a lock of another resource at a next particular program location. If directed edges between two or more nodes in the graph form a closed directed loop, or the graph has a strongly connected sub graph, it indicates that the program has deadlock, and thus deadlock may be detected by checking whether a directed loop exists in the graph. The concept of strongly connected sub graph will be introduced hereinafter.
The above graph theory based deadlock detection method in the prior art has the following problems: currently, the code quantity for many large programs is bulky, and the processes (threads) involved during program running are great, and accordingly, the quantity of the requirements on resources (locks) by the processes (threads) is also very large. In this case, the quantity of nodes (locks) of the generated lock graph will be very great, so is the quantity of directed edges (a process having obtained a lock of a certain resource is requesting a lock of another resource). Therefore, generation of the lock graph will waste a great amount of time and system resources; meanwhile, the work of retrieving or extracting a strongly connected sub graph or closed loop from the generated complicated lock graph will also consume a great amount of time and system resources. In other words, to detect a currently popular large program with the graph theory based deadlock detection method in the prior art is extremely time consuming, resource consuming, and rather uneconomic.